/*
 * Hash.hpp
 *
 *  Created on: 18 déc. 2011
 *      Author: Elca
 */

#ifndef HASH_HPP_
#define HASH_HPP_

#define MAXLOAD 2


#include "HashNode.hpp"
#include <cstdlib>
#include <cstring>
#include <iostream>
#include "def.hpp"
using namespace std;
namespace pcm {

typedef union{
	HashNode*node;
	LL value;
} HashNodeConversion;


class Hash {
public:
	Hash();
	virtual ~Hash();

	HashNode*** m_primaryBuckets;
	int m_itemCount;
	int m_size;

	/**
	 * crée table primaire, table secondaire et la sentinelle 0. Doit être appelée avant toute autre fonction
	 * agissant sur la table
	 * @return true si pas de problème de malloc, false autrement
	 */
	inline bool initialize(){
		m_primaryBuckets = (HashNode***)calloc(48,sizeof(HashNode **));
		if(m_primaryBuckets!=NULL){
			m_primaryBuckets[0] =(HashNode**)calloc(m_size,sizeof(HashNode *));
			if(m_primaryBuckets[0]!=NULL){
				m_primaryBuckets[0][0] =(HashNode*)malloc(sizeof(HashNode));
				if(m_primaryBuckets[0][0]!=NULL){
					m_primaryBuckets[0][0]->m_sentinel = true;
					m_primaryBuckets[0][0]->m_next = NULL;
					m_primaryBuckets[0][0]->m_reversedKey=0;
					m_primaryBuckets[0][0]->m_item = NULL;

					return true;
				}
				free(m_primaryBuckets[0]);
			}
			free(m_primaryBuckets);
		}
		return false;
	}

	/**
	 * Crée une sentinelle et l'insère dans la liste. C'est ensuite à l'appelant d'insérer la sentinelle dans
	 * la table secondaire
	 * @return Noeud sentinelle crée
	 */
	inline HashNode* initializeBucket(LL _key){
		HashNode *sentinel, *parentBucket, *pred;
		LL parent = m_size;
		while((parent = parent>>1)> _key);
		parentBucket = getSecondaryBucket(_key-parent);
		if((sentinel = (HashNode*)malloc(sizeof(HashNode))) != NULL){
			sentinel->m_sentinel = true;
			sentinel->m_item = NULL;
			sentinel->m_reversedKey = _key = BoardInfos::reverseAllBoard(_key);//reverse64(_key);
			sentinel->m_next = NULL;
			if(!listInsert(parentBucket,sentinel)) {
				free(sentinel);
				if(!find(parentBucket,_key,true,&pred,&sentinel)){
					return NULL;
				}
			}
		}
		return sentinel;
	}

	/**
	 * Retourne la sentinelle ou débute toutes les opérations Add, Contains, Remove
	 */
	inline HashNode* getSecondaryBucket(LL _key){
		LL i,min,max;
		HashNode **secondary,*sentinel;
		for(i=min=0,max=2;_key>=max;i+=1,max<<=1){
			min=max;
		}
		if(m_primaryBuckets[i]==NULL){
			secondary = (HashNode**)calloc(m_size>>1,sizeof(HashNode*));
			if(secondary==NULL) return NULL;
			bool hascas = bcasptr(&m_primaryBuckets[i],NULL,secondary);
			if(!hascas){
				free(secondary);
			}
		}
		if(m_primaryBuckets[i][_key-min]==NULL){
			if((sentinel=initializeBucket(_key))!=NULL){
				m_primaryBuckets[i][_key-min] = sentinel;
			}
		}
		return m_primaryBuckets[i][_key-min];
	}

	inline BoardInfos* getItem(LL _key){
		HashNode *p, *c;
		HashNode* bucket = getSecondaryBucket(_key%m_size);
		if(bucket==NULL){
			return NULL;
		}
		bool hasfind = find(bucket,BoardInfos::reverseAllBoard(_key),false,&p,&c);
		if(hasfind){
			return c->m_item;
		}else{
			return NULL;
		}
		return c->m_item;
	}
	/**
	 * Insert un noeud dans la liste à partir de la sentinelle head
	 * @return true si le noeud a été inséré et false s'il s'agit d'un doublon
	 */
	inline bool listInsert(HashNode *_head,HashNode *_node){
		HashNode *p, *c;
		while(true){
			bool hasfind = find(_head,_node->m_reversedKey,_node->m_sentinel,&p,&c);
			if(hasfind){
				return false;
			}
			_node->m_next=c;
			bool hascas = bcasptr(&p->m_next,c,_node);
			if(hascas){
				return true;
			}
		}
	}

	/**
	 * Parcourt la liste depuis la sentinelle head à la recherche des noeuds précédent(pred) et suivant(curr) à
	 * celui recherché et qui est identifié par sa clé inverse(rKey)
	 * @return true si la clé est déjà contenue dans la liste, curr dans ce cas désigne le noeud recherché;
	 * false si la clé n'est pas contenue dans la liste, dans ce cas pred et curr désignent les noeuds ou
	 * il peut y avoir une insertion
	 */
	inline bool find(HashNode *head, LL rKey,bool isSent,HashNode**pred,HashNode**curr){
		HashNodeConversion next;
		while(true) {
			*pred = head;
			*curr=(*pred)->m_next;
			while(true){
				if(*curr==NULL){
					return false;
				}
				next.node = (*curr)->m_next;
				if(next.value&0x1){
					next.value ^= 0x1;
					bool hascas = casptr(&(*pred)->m_next,*curr,next.node);
					if(hascas){
						*curr = next.node;
					}else{
						break;
					}
				}else if((*curr)->m_reversedKey==rKey && isSent == (*curr)->m_sentinel){
					return true;
				}else if((*curr)->m_reversedKey==rKey &&isSent){
					return false;
				}else if((*curr)->m_reversedKey>rKey){
					return false;
				}else{
					*pred = *curr;
					*curr = next.node;
				}
			}
		}
		return false;
	}

	/**
	 *
	 */
	inline bool add(BoardInfos* item){
		cout <<"item:"<<item->board()<<endl;
		HashNode* bucket,*newNode;
		LL size, key;
		if((newNode=(HashNode*)malloc(sizeof(HashNode)))==NULL){
			return false;
		}

		newNode->m_sentinel=false;
		key= item->board();//hashCode(item);
		newNode->m_reversedKey = BoardInfos::reverseAllBoard(key);//reverse64(key);
		newNode->m_item = item;
		if((bucket=getSecondaryBucket(key%m_size))==NULL){
			return false;
		}
		cout <<"bucket: issent:"<<bucket->m_sentinel<<" rkey:"<<bucket->m_reversedKey<<" boardp:"<<bucket->m_item<<endl;
		cout <<"newnod: issent:"<<newNode->m_sentinel<<" rkey:"<<newNode->m_reversedKey<<" boardp:"<<newNode->m_item<<endl;
		if(!listInsert(bucket,newNode)){
			free(newNode);
			return false;
		}
		size = m_size;
		if(AtomicFetchAndIncrement(&m_itemCount,1)/size>=MAXLOAD){
			cas64(&m_size,size,size*2);
		}
		return true;
	}

	inline bool remove(BoardInfos* item){
		HashNode* pred, *curr, *bucket, *tmpNext;
		HashNodeConversion next;
		LL key = item->board();//hashCode(item);
		if((bucket = getSecondaryBucket(key%m_size))==NULL){
			return false;
		}
		key = BoardInfos::reverseAllBoard(key);//reverse64(key);
		while(true){
			if(!find(bucket,key,false,&pred,&curr)){
				return false;
			}
			next.node = tmpNext = curr->m_next;
			if((next.value &0x1)== 0){
				next.value |= 0x1;
				bool hascas = bcasptr(&curr->m_next,tmpNext,next.node);
				if(hascas){
					casptr(&pred->m_next,curr,tmpNext);
					AtomicFetchAndDecrement(&m_itemCount,1);
					return true;
				}
			}
		}
		return false;
	}
};

} /* namespace pcm */
#endif /* HASH_HPP_ */
